package week02

// 450. 删除二叉搜索树中的节点
// https://leetcode-cn.com/problems/delete-node-in-a-bst/

func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val == key {
		if root.Left == nil {
			return root.Right
		}
		if root.Right == nil {
			return root.Left
		}
		r := root.Right
		for r.Left != nil {
			r = r.Left
		}
		root.Right = deleteNode(root.Right, r.Val)
		root.Val = r.Val
	}
	if root.Val > key {
		root.Left = deleteNode(root.Left, key)
	}
	if root.Val < key {
		root.Right = deleteNode(root.Right, key)
	}
	return root
}

type TreeNode struct {
	Val int
	Left, Right *TreeNode
}